#
# @lc app=leetcode.cn id=70 lang=python3
#
# [70] 爬楼梯
#

# @lc code=start
class Solution:
    def climbStairs(self, n: int) -> int:
        #solution1: 递归求解，超时，无法通过
        # def f(n):
        #     if n == 1: 
        #         return 1
        #     elif n == 2: 
        #         return 2
        #     else:
        #         return f(n-1) + f(n-2)
        
        # return f(n) 
        
        #solution2:动态规划
        # f2 = 0
        # f1 = 0
        # r = 1
        # for i in range(1,n+1):
        #     f1 = f2
        #     f2 = r
        #     r = f2 + f1
        # return r
        #soulution3:矩阵乘法
        # import numpy as np
        # a = np.matrix([[1,1], [1,0]])
        # r = np.matrix([[1,1], [1,0]])
        # b = np.matrix([[1], [1]])
        # for i in range(n-1):
        #     r = np.dot(r,a)
        # r = np.dot(r,b)
        
        # return int(r[1])  
        
        import numpy as np
        a = np.matrix([[1,1], [1,0]])
        b = np.matrix([[1], [1]])
        r = np.matrix([[1,1], [1,0]])
        a = a**n*b
        return int(a[1])
# @lc code=end

